7.9 Ejemplo de ABB en C  

Vamos a ver cómo implementar en C algunas de las funciones que hemos explicado para árboles ABB, al final se incluye un ejemplo completo para árboles de enteros.

Declaración de tipos:

Como estamos trabajando con un árbol binario, sólo necesitamos una estructura para referirnos tanto a cualquiera de los nodos como al árbol completo. Recuerda que cualquier nodo puede ser considerado como la raíz de un árbol.

typedef struct _nodo {
   int dato;
   struct _nodo *derecho;
   struct _nodo *izquierdo;
} tipoNodo;
 
typedef tipoNodo *pNodo;
typedef tipoNodo *Arbol;

Insertar un elemento en un árbol ABB:

Diseñaremos una función que se ajuste al algoritmo que describimos en el punto 7.4:

1. Padre = NULL
2. nodo = Raiz
3. Bucle: mientras actual no sea un árbol vacío o hasta que se encuentre el elemento.
   1. Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo: Padre=nodo, nodo=nodo->izquierdo.
   2. Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho: Padre=nodo, nodo=nodo->derecho.
4. Si nodo no es NULL, el elemento está en el árbol, por lo tanto salimos.
5. Si Padre es NULL, el árbol estaba vacío, por lo tanto, el nuevo árbol sólo contendrá el nuevo elemento, que será la raíz del árbol.
6. Si el elemento es menor que el Padre, entonces insertamos el nuevo elemento como un nuevo árbol izquierdo de Padre.
7. Si el elemento es mayor que el Padre, entonces insertamos el nuevo elemento como un nuevo árbol derecho de Padre.

void Insertar(Arbol *a, int dat) {
   pNodo padre = NULL; /* (1) */
   pNodo actual = *a;  /* (2) */

   while(!Vacio(actual) && dat != actual->dato) {  /* (3) */
      padre = actual;
      if(dat < actual->dato) actual = actual->izquierdo;  /* (3-a) */
      else if(dat > actual->dato) actual = actual->derecho; /* (3-b) */
   }

   if(!Vacio(actual)) return;  /* (4) */
   if(Vacio(padre)) {  /* (5) */
      *a = (Arbol)malloc(sizeof(tipoNodo));
      (*a)->dato = dat;
      (*a)->izquierdo = (*a)->derecho = NULL;
   }
   else if(dat < padre->dato) { /* (6) */
      actual = (Arbol)malloc(sizeof(tipoNodo));
      padre->izquierdo = actual;
      actual->dato = dat;
      actual->izquierdo = actual->derecho = NULL;
   }
   else if(dat > padre->dato) { /* (7) */
      actual = (Arbol)malloc(sizeof(tipoNodo));
      padre->derecho = actual;
      actual->dato = dat;
      actual->izquierdo = actual->derecho = NULL;
  }
}

Eliminar un elemento de un árbol ABB:

Diseñaremos una función que se ajuste al algoritmo que describimos en el punto 7.5:

1. Padre = NULL
2. Si el árbol está vacío: el elemento no está en el árbol, por lo tanto salimos sin eliminar ningún elemento.
3. Si el valor del nodo raíz es igual que el del elemento que buscamos, estamos ante uno de los siguientes casos:
   1. El nodo raíz es un nodo hoja:
      1. Si 'Padre' es NULL, el nodo raíz es el único del árbol, por lo tanto el puntero al árbol debe ser NULL.
      2. Si raíz es la rama derecha de 'Padre', hacemos que esa rama apunte a NULL.
      3. Si raíz es la rama izquierda de 'Padre', hacemos que esa rama apunte a NULL.
      4. Eliminamos el nodo, y salimos.
   2. El nodo no es un nodo hoja:
      1. Buscamos el 'nodo' más a la izquierda del árbol derecho de raíz o el más a la derecha del árbol izquierdo. Hay que tener en cuenta que puede que sólo exista uno de esos árboles. Al mismo tiempo, actualizamos 'Padre' para que apunte al padre de 'nodo'.
      2. Intercambiamos los elementos de los nodos raíz y 'nodo'.
      3. Borramos el nodo 'nodo'. Esto significa volver a (3), ya que puede suceder que 'nodo' no sea un nodo hoja.
4. Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.
5. Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.

void Borrar(Arbol *a, int dat) {
   pNodo padre = NULL; /* (1) */
   pNodo actual;
   pNodo nodo;
   int aux;

   actual = *a;
   while(!Vacio(actual)) { /* Búsqueda (2) else implícito */
      if(dat == actual->dato) { /* (3) */
         if(EsHoja(actual)) { /* (3-a) */
            if(padre)/* (3-a-i caso else implícito) */
               if(padre->derecho == actual) padre->derecho = NULL;  /* (3-a-ii) */
               else if(padre->izquierdo == actual) padre->izquierdo = NULL; /* (3-a-iii) */
            free(actual); /* (3-a-iv) */
            actual = NULL; 
            return;
         }
         else { /* (3-b) */
            /* Buscar nodo */
            padre = actual; /* (3-b-i) */
            if(actual->derecho) {
               nodo = actual->derecho;
               while(nodo->izquierdo) {
                  padre = nodo;
                  nodo = nodo->izquierdo;
               }
            }
            else {
               nodo = actual->izquierdo;
               while(nodo->derecho) {
                  padre = nodo;
                  nodo = nodo->derecho;
               }
            }
            /* Intercambio */
            aux = actual->dato; /* (3-b-ii) */
            actual->dato = nodo->dato;
            nodo->dato = aux;
            actual = nodo;
         }
      }
      else {
         padre = actual;
         if(dat > actual->dato) actual = actual->derecho; /* (4) */
         else if(dat < actual->dato) actual = actual->izquierdo; /* (5) */
      }
   }
}

Buscar un elemento en un árbol ABB:

Diseñaremos una función que se ajuste al algoritmo que describimos en el punto 7.3:

1. Si el árbol está vacío, terminamos la búsqueda: el elemento no está en el árbol.
2. Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda con éxito.
3. Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.
4. Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.

int Buscar(Arbol a, int dat) {
   pNodo actual = a;

   while(!Vacio(actual)) {
      if(dat == actual->dato) return TRUE; /* dato encontrado  (2) */
      else if(dat < actual->dato) actual = actual->izquierdo;  /* (3) */
      else if(dat > actual->dato) actual = actual->derecho; /* (4) */
   }
   return FALSE; /* No está en árbol (1) */
}

Comprobar si el árbol está vacío:

Esta función es fácil de implementar:

int Vacio(Arbol r) {
   return r==NULL;
}

Comprobar si un nodo es hoja:

Esta función también es sencilla de implementar:

int EsHoja(pNodo r) {
   return !r->derecho && !r->izquierdo;
}

Contar número de nodos:

En el punto 7.7 comentábamos que para contar los nodos podemos recurrir a cualquiera de los tres modos de recorrer el árbol: inorden, preorden o postorden y como acción incrementamos el contador de nodos. Para implementar este algoritmo recurrimos a dos funciones:

int NumeroNodos(Arbol a, int *contador) {
   *contador = 0;

   auxContador(a, contador);
   return *contador;
}

void auxContador(Arbol nodo, int *c) {
   (*c)++; /* Acción: incrementar número de nodos. (Preorden) */
   if(nodo->izquierdo) auxContador(nodo->izquierdo, c); /* Rama izquierda */
   if(nodo->derecho)   auxContador(nodo->derecho, c);   /* Rama derecha */
}

Calcular la altura de un árbol:

Es un problema parecido al anterior, pero ahora tenemos que contar la altura, no en número de nodos. Cada vez que lleguemos a un nodo hoja, verificamos si la altura del nodo es la máxima, y si lo es, actualizamos la altura del árbol a ese valor:

1. Iniciamos un recorrido del árbol en postorden, con la variable de altura igual a cero.
2. Cada vez que empecemos a recorrer una nueva rama, incrementamos la altura para ese nodo.
3. Después de procesar las dos ramas, verificamos si la altura del nodo es mayor que la variable que almacena la altura actual del árbol, si es así, actualizamos esa variable.

int AlturaArbol(Arbol a, int *altura) {
   *altura = 0; /* (1) */

   auxAltura(a, 0, altura);
   return *altura;
}

void auxAltura(pNodo nodo, int a, int *altura) {
   /* (2) Cada vez que llamamos a auxAltura pasamos como parámetro a+1 */
   if(nodo->izquierdo) auxAltura(nodo->izquierdo, a+1, altura); /* Rama izquierda */
   if(nodo->derecho)   auxAltura(nodo->derecho, a+1, altura);   /* Rama derecha */
   if(EsHoja(nodo) && a > *altura) *altura = a; /* Proceso (Postorden)  (3) */
}

Calcular la altura del nodo que contienen un dato concreto:

Lo que haremos será buscar el elemento del nodo del que queremos averiguar la altura. Cada vez que avancemos un nodo incrementamos la variable que contendrá la altura del nodo.

1. Empezamos con el nodo raíz apuntando a Raiz, y la 'Altura' igual a cero.
2. Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda y el valor de la altura es 'Altura'.
3. Incrementamos 'Altura'.
4. Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.
5. Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.

int Altura(Arbol a, int dat) {
   int altura = 0; 
   pNodo actual = a; /* (1) */

   while(!Vacio(actual)) {
      if(dat == actual->dato) return altura; /* dato encontrado. (2) */
      else {
         altura++; /* (3) */
         if(dat < actual->dato) actual = actual->izquierdo; /* (4) */
         else if(dat > actual->dato) actual = actual->derecho; /* (5) */
      }
   }
   return -1; /* No está en árbol */
}

Aplicar una función a cada elemento del árbol, según los tres posibles recorridos:

Todos los recorridos se aplican de forma recursiva. En este ejemplo crearemos tres funciones, una por cada tipo de recorrido, que aplicarán una función al elemento de cada nodo.

La función a aplicar puede ser cualquiera que admita como parámetro un puntero a un entero, y que no tenga valor de retorno.

InOrden

En Inorden, primero procesamos el subárbol izquierdo, después el nodo actual, y finalmente el subárbol derecho:

void InOrden(Arbol a, void (*func)(int*)) {
   if(a->izquierdo) InOrden(a->izquierdo, func); /* Subárbol izquierdo */
   func(&(a->dato)); /* Aplicar la función al dato del nodo actual */
   if(a->derecho) InOrden(a->derecho, func);     /* Subárbol derecho */
}

PreOrden

En Preorden, primero procesamos el nodo actual, después el subárbol izquierdo, y finalmente el subárbol derecho:

void PreOrden(Arbol a, void (*func)(int*)) {
   func(&(a->dato)); /* Aplicar la función al dato del nodo actual */
   if(a->izquierdo) PreOrden(a->izquierdo, func); /* Subárbol izquierdo */
   if(a->derecho) PreOrden(a->derecho, func);     /* Subárbol derecho */
}

PostOrden

En Postorden, primero procesamos el subárbol izquierdo, después el subárbol derecho, y finalmente el nodo actual:

void PostOrden(Arbol a, void (*func)(int*)) {
   if(a->izquierdo) PostOrden(a->izquierdo, func); /* Subárbol izquierdo */
   if(a->derecho) PostOrden(a->derecho, func);     /* Subárbol derecho */
   func(&(a->dato)); /* Aplicar la función al dato del nodo actual */
}

Fichero con el código fuente: